//
// Created by Administrator on 2021/4/6.
//

/*
给定一个二叉树，检查它是否是镜像对称的。


例如，二叉树[1,2,2,3,4,4,3] 是对称的。

1
/ \
  2   2
/ \ / \
3  4 4  3


但是下面这个[1,2,2,null,3,null,3] 则不是镜像对称的:

1
/ \
  2   2
\   \
   3    3

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xoxzgv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/

#include <iostream>
#include <queue>
using namespace std;

// 树节点定义
struct TreeNode {
    int val; // 节点值
    TreeNode *left; // 左子节点
    TreeNode *right; // 右子节点

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    bool isMirror(TreeNode *left, TreeNode *right) {
        if (left == nullptr and right == nullptr) return true; // 两个都为空 ok
        if (left == nullptr or right == nullptr) return false; // 只有一个为空 不对称
        // 左值=右值  左子节点的左子树=右子节点的右子树 左子节点的右子树=右子节点的左子树
        return (left->val == right->val and isMirror(left->left, right->right) and isMirror(left->right, right->left));
    }

    bool isSymmetric(TreeNode *root) { //递归 镜像对称 ？
//        判断二叉树是否是对称，需要从子节点开始比较，两个子节点的值必须相同，
//        并且左子节点的右子节点（如果有）必须等于右子节点的左子节点，左子节点的左子节点必须等于右子节点的右子节点。
        return isMirror(root, root); // 初始时用根节点比较
    }

};
class Solution2 {  // 题解 迭代 队列解决
public:
    bool check(TreeNode *u, TreeNode *v) {
        queue <TreeNode*> q;
        q.push(u); q.push(v);
        while (!q.empty()) {
            // 每次取出两个进行比较
            u = q.front(); q.pop();
            v = q.front(); q.pop();
            if (!u && !v) continue; // 两个空节点
            if ((!u || !v) || (u->val != v->val)) return false; // 只有一个空节点 或者值不相等

            q.push(u->left);
            q.push(v->right);

            q.push(u->right);
            q.push(v->left);
        }
        return true;
    }

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};

int main() {
    auto t7 = TreeNode(3);
    auto t6 = TreeNode(4);
    auto t5 = TreeNode(4);
    auto t4 = TreeNode(3);
    auto t3 = TreeNode(2, &t6, &t7);
    auto t2 = TreeNode(2, &t4, &t5);
    auto t1 = TreeNode(1, &t2, &t3);
    Solution sol;
    cout << sol.isSymmetric(&t1);
    return 0;
}